import { Node } from './singleLinkList'


/**
 * 反转链表(递归形式)
 * e.g. 3 -> 4 -> 5 -> 6 -> null =>   6 -> 5  -> 4 -> 3 -> null  
 * @param ll 
 */
export const reverse = <T>(head: Node<T> | null): Node<T> | null => {
    // head === null 和 head.next === null 保证了head至少有两个元素 
    if (head === null || head.next === null) return head;
    // 1. 一直找到最后的next
    const nextNode = reverse(head.next);
    // 处理当前的节点head, 当前节点仍然保持了自己的next节点，可能存在两个节点指向同一个节点，此时操作的仍然是同一个节点
    head.next.next = head;
    // 清空自己的next
    head.next = null

    return nextNode
}


/**
 * 通过迭代的方式反转链表
 * e.g. 3 -> 4 -> 5 -> 6 -> null =>   6 -> 5  -> 4 -> 3 -> null  
 * 新建一个头，从左向右遍历原链表， 取出原来的头节点，next指向newHead, 然后newHead重新指向为该头节点，这样逐步转移
 * 注意点:   1. 保存头节点的下一个节点   2. 改变newHead的指向为取出的头节点， 头节点的下一个节点指向原来的newHead 
 * 
 * @param head 
 */
export const reverseUseIterator = <T>(head: Node<T> | null): Node<T> | null => {
    // 边界判断
    if (head === null || head.next === null) return head;
    // console.log(head)

    // 新的链表
    let newHead = null;
    while (head !== null) {
        // 保存head的next
        const prev: Node<T> | null = head.next;

        head.next = newHead
        newHead = head;

        // 原来的头指向下一个节点
        head = prev
    }
    return newHead
}







